树与二叉树

发表于 | 更新于: | 分类于
字数统计: 2,066 字

1 树的基本概念

1.1树的定义

树是N(N>=0)个结点的有限集合，N=0时，称为空树。任意一棵非空树满足：

  1. 有且仅有一个特定的称为根的结点。
  2. 当N>1时，其余结点可分为m个互不相交的有限集合，其中每个集合本身又是一棵树，并且称为根结点的子树。

树具有以下特点：

  1. 树的根结点没有前驱结点，除根以外的结点有且仅有一个前驱结点。
  2. 树中结点可以有零个或多个后结点。

1.2基本术语

  1. 结点关系：
    • 祖先结点
    • 子孙结点
    • 双亲结点
    • 孩子结点
    • 兄弟结点
  2. 度：
    • 结点的度：一个结点的子结点个数
    • 树的度：Max{结点的度}
    • 分支结点：度大于0的结点
    • 叶子节点：度为0的结点
  3. 结点属性：
    • 结点的深度：从根结点开始自顶向下逐层累加
    • 结点的高度：从叶子结点开始自底向上逐层累加
    • 树的高度：树中结点的最大层数
  4. 路径：
    • 路径：路径由两个结点之间所经过的结点序列构成
    • 路径长度：路径所经过的边的个数
  5. 森林：树的集合

1.3树的性质

  1. 树的结点树等于所有结点的度数之和加1。
  2. 度为m的树树中，第i层最多有mi-1 个结点(i>=1)
  3. 高度为h的m叉树最多有(m h -1)/(m-1)个结点(等比数列求和)
  4. 具有n个结点的m叉树的最小高度为logm(n(m-1)+1)向上取整(由3中公式推倒)

2 二叉树

2.1 二叉树的定义及其主要性质

  1. 二叉树的定义
    • 或者为空二叉树。
    • 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成，左子树和右子树又分别为一颗二叉树。
  2. 特殊二叉树
    满二叉树：树中每一层都含有最多结点，一颗高为h的满二叉树含有2h-1个结点。
    完全二叉树：高度为h，有n个结点的二叉树，当且仅当每一个结点都与高度相同的满二叉树中编号为1~n的结点一一对应，称为完全二叉树。
    二叉排序树：二叉排序树的左子树上所有结点的关键字均小于根结点的关键字而右结点相反，左子树和右子树又各是一颗二叉树；或者是一颗空二叉树。
    平衡二叉树：树上任意结点的左子树和右子树的深度之差不超过1。
  3. 二叉树的性质
  • 非空二叉树中叶子结点数N0等于度为2的结点数N2加1,即N0=N2+1;
    • N0+N1+N2=N;N-1=N1+2N2;
  • 第K层至多有2K-1个结点(K>=1);
  • 高度为H的二叉树至多有2H-1个结点(H>=1);
  • 完全二叉树：
    • 结点i的左孩子编号为2i，或者无左孩子；
    • 结点i的右孩子为2i+1，或者无右孩子；
    • 结点i所在深度为log2i+1(向下取整)；

2.2 二叉树的存储结构

  1. 顺序存储结构
    适用于完全二叉树或满二叉树，将编号为i的结点元素存储在数组下标为i-1的分量中(或者从下标1开始存储）。

  2. 链式存储结构
    结点结构：

    • 数据域data
    • 左指针域lchild
    • 右指针域rchlid

  3. 二叉树的链式存储结构描述

    1
    2
    3
    4
    typedef struct BiTNode{
        ElemType data;
        struct BiTNode *lchild,rchild;
    }BitNode,*BitTree;

    含n个结点的二叉链表中含n+1个空链域。

3 二叉树的遍历和线索二叉树

3.1 二叉树的遍历

  1. 先序遍历(PreOrder)

    1
    2
    3
    4
    5
    6
    7
    void PreOrder(BitTree T){
        if(T!=NULL){
            visit(T);
            PreOrder(T->lchild);
            PreOrder(T->rchild);
        }
    }

  2. 中序遍历(InOrder)

    1
    2
    3
    4
    5
    6
    7
    void InOrder(BitTree T){
        if(T!=NULL){
            InOrder(T->lchild);
            visit(T);
            InOrder(T->rchild);
        }
    }

  3. 后序遍历(PostOrder)

    1
    2
    3
    4
    5
    void PostOrder(BitTree T){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }

  4. 递归算法和非递归算法的转换
    借助栈实现树的非递归算法
    中序遍历

     
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void InOrder2(BitTree T){
        InitStack S;            //初始化栈
        BiTNode *p = T;         //p为遍历指针
        while(p||!IsEmpty(S)){    //栈不空或p指针不空时循环
            if(P){                  //根指针进栈，遍历左子树
                Push(S,p);          //往左走到底
                p=p->rchild;
            }
            else{                   //指针出栈并访问，遍历右子树
                Pop(S,p);
                visit(p);
                p=p->rchild;
            }
        }
    }

    前序遍历

     
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void PreOrder2(BitTree T){
        InitStack(S):
        BiTNode *p = T;
        while(p||!IsEmpty(S)){
            if(p){
                Push(S,p);
                visit(p);
                p=p->lchild;
            }
            else{
               Pop(S,p);
               p=p->rchild;       
            }
        }
    }

    后序遍历
    思路：对于任意一个结点P，访问顺序是：P->lchild、P->rchild、p。所以入栈顺序相反；对P进行访问当且仅当其左右孩子均已被访问或左右孩子不存在，故在左右孩子入栈时可以将P的左右孩子置空，表示左右孩子已访问。

     
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    void PostOrder2(BitTree T){
        InitStack(S);
        BiTNode *p = T;
        Pop(S,p);
        while(!IsEmpty(S)){
            GetTop(S,p);
            if(p->rchild==NULL&&p->lchild==NULL){
                visit(p);
                Pop(S,p);
            }
            else{
                if(p->rchild){              //先压如右孩子，再压入左孩子
                    Push(S,p->rchild);    
                    p->rchild==NULL;      //由于右孩子必定先与父结点被访问，
                }                        //改变父结点的链接关系不会影响访问顺序
                if(p->lchild){
                    Push(S,p->lchild);
                    p->lchild==NULL;
                }
            }
        }
    }

  5. 层次遍历
    借助队列实现层次遍历算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void LevelOrder(BitTree T){
        InitQueue(Q);
        BitTree p;
        EnQueue(Q,p);
        while(!IsEmpty(Q)){
            DeQueue(Q,p);
            visit(p);
            if(p->lchild)
                EnQueue(p->lchild);
            if(p->rchild)
                EnQueue(p->rchild);
        }
    }

  6. 由遍历序列构造二叉树
    由二叉树的中序序列与先序序列、后序序列或层序序列三者之一可唯一确定一颗二叉树。
    由先序序列和后序序列无法唯一确定一颗二叉树。

3.2 线索二叉树

线索二叉树存储结构描述：

1
2
3
4
5
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,rchild;   //左右孩子指针
    int ltag，rtag                      //左右线索标志
}ThreadNode，*ThreadTree;

其中：ltag=0表示lchild域指示结点的左孩子，ltag=1表示lchild域指示结点的前驱；
rtag=0表示rchlid域指示结点的右孩子，rtag=2表示rchlid域指示结点的后继。

4 树和森林

4.1 树的存储结构

  1. 双亲表示法
    采用一组连续空间存储每个结点，每个结点设一伪指针，指示其双亲结点在数组中的位置
  2. 孩子表示法
    将每个结点的孩子结点用单链表链接形成线性结构
  3. 孩子兄弟表示法(二叉树表示法)
    每个结点包含结点值、指向第一个孩子结点的指针和指向下一个兄弟结点的指针。

4.2 树、森林与二叉树的转换

  1. 树转二叉树：
    每个结点的左指针指向它的第一个孩子结点，右指针指向它在树中相邻的兄弟结点。即左孩子右兄弟，树转换而得的二叉树无右子树。
  2. 森林转换成二叉树
    在树转换成二叉树的基础上，将第i+1颗树作为第i颗树的右子树。
  3. 二叉树转换为树或森林

4.3 树和森林的遍历

树的遍历

  1. 先根遍历
    先访问根结点再从左到右遍历子树，同相应二叉树的先序遍历
  2. 后根遍历
    先从左到右遍历子树再访问根结点，同相应二叉树的中序遍历

森林的遍历

  1. 先序遍历森林
  2. 中序遍历森林

树和森林的遍历与二叉树遍历的对应关系
|树|森林|二叉树|
|—-|—-|—-|
|先根遍历|先序遍历|先序遍历|
|后根遍历|中序遍历|中序遍历|

4.4 树的应用——并查集